package sort;

import java.util.Arrays;

/**
 * 平均 O(nlogn)
 * 最好 O(nlogn)
 * 最坏 O(nlogn)
 * 空间 O(1)
 * 排序方式 in-place
 * 稳定性 不稳定
 */
public class HEAP {
    private int [] a = {1,6,2,4,1,5,9};

    private void sort(){
        heapSort();
    }

    public void heapSort() {
        int len = a.length;
        if (len < 1) return;
        //1.构建一个最大堆
        buildMaxHeap();
        //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
        while (len > 0) {
            swap(0, len - 1);
            len--;
            adjustHeap(0, len);
        }
    }
    /**
     * 建立最大堆
     */
    public  void buildMaxHeap() {
        //从最后一个非叶子节点开始向上构造最大堆
        for (int i = (a.length/2 - 1); i >= 0; i--) { //感谢 @让我发会呆 网友的提醒，此处应该为 i = (len/2 - 1)
            adjustHeap(i, a.length);
        }
    }
    /**
     * 调整使之成为最大堆
     */
    public void adjustHeap(int i, int len) {
        int maxIndex = i;
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (i * 2 + 1 < len && a[i * 2 + 1] > a[maxIndex])
            maxIndex = i * 2 + 1;
        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if (i * 2 + 2 < len && a[i * 2 + 2] > a[maxIndex])
            maxIndex = i * 2 + 2;
        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
        if (maxIndex != i) {
            swap(maxIndex, i);
            adjustHeap(maxIndex, len);
        }
    }

    public void swap(int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private void print(){
        System.out.println(Arrays.toString(a));
    }
    public static void main(String [] args){
        HEAP maoPao = new HEAP();
        maoPao.print();
        maoPao.sort();
        maoPao.print();
    }
}
